Parallel clustering of high-dimensional social media data streams

摘要

We introduce Cloud DIKW as an analysis environment supporting scientificdiscovery through integrated parallel batch and streaming processing, and applyit to one representative domain application: social media data streamclustering. Recent work demonstrated that high-quality clusters can begenerated by representing the data points using high-dimensional vectors thatreflect textual content and social network information. Due to the high cost ofsimilarity computation, sequential implementations of even single-passalgorithms cannot keep up with the speed of real-world streams. This paperpresents our efforts to meet the constraints of real-time social streamclustering through parallelization. We focus on two system-level issues. Moststream processing engines like Apache Storm organize distributed workers in theform of a directed acyclic graph, making it difficult to dynamicallysynchronize the state of parallel workers. We tackle this challenge by creatinga separate synchronization channel using a pub-sub messaging system. Due to thesparsity of the high-dimensional vectors, the size of centroids grows quicklyas new data points are assigned to the clusters. Traditional synchronizationthat directly broadcasts cluster centroids becomes too expensive and limits thescalability of the parallel algorithm. We address this problem by communicatingonly dynamic changes of the clusters rather than the whole centroid vectors.Our algorithm under Cloud DIKW can process the Twitter 10% data stream inreal-time with 96-way parallelism. By natural improvements to Cloud DIKW,including advanced collective communication techniques developed in our Harpproject, we will be able to process the full Twitter stream in real-time with1000-way parallelism. Our use of powerful general software subsystems willenable many other applications that need integration of streaming and batchdata analytics.